﻿/*本程序的功能是完成闭散列表的建立,输出和查找.
  散列表长度为m, 散列函数： H(key) = key MOD p,
  m和p的值作为构造函数参数输入,散列表空时,元素
  值为-99
*/
#include <iostream>
#include <stdio.h>
using namespace std;
class HashTable
{
private:
    int* hash;
    int m;
    int p;
public:
    HashTable(int mt, int pt);
    ~HashTable() { delete[]hash; };
    void createHT();    //建立散列表
    void htOut();       //输出散列表
    int searchHT(int x);//查找不成功，返回-1;查找成功，返回下标值
};

HashTable::HashTable(int mt, int pt)
{
    int i;
    m = mt;
    p = pt;
    hash = new int[m];
    for (i = 0; i < m; i++) //散列表清空
        hash[i] = -99;
}

void HashTable::createHT()
{
    int j, k;
    cout << "请输入查找表元素(整数),用空格分开,以-1结束:" << '\n';
    cin >> j;
    while (j != -1)
    {
        k = j % p;                          /*散列函数： H(key) = key MOD p*/
        if (hash[k] == -99)
            hash[k] = j;
        else
        {
            k = (k + 1) % m;               /*发生冲突，用线性探测法解决*/
            while (hash[k] != -99)
                k = (k + 1) % m;
            hash[k] = j;
        }
        cin >> j;                      /*输入闭散列表元素值*/
    }
}

void HashTable::htOut()
{/*显示闭散列表*/
    int i;
    for (i = 0; i < m; i++)
        printf("%5d", i);
    printf("\n\n");
    for (i = 0; i < m; i++)
        if (hash[i] != -99)
            printf("%5d", hash[i]);
        else
            printf("%5c", ' ');
    printf("\n\n");
}

int HashTable::searchHT(int k)
{/*闭散列表中查找元素*/
    int  i, j;
    i = 0;
    j = k % p;            /*散列函数： H(key) = key MOD p*/
    while (i < m && hash[j] != k && hash[j] != -99)
    {
        i++;
        j = (j + 1) % m;
    }   /*发生冲突，用线性探测法解决*/
    if (hash[j] != k) return -1;     /*查找不成功，返回 -1*/
    else return j;                 /*查找成功，返回下标值*/
}

void main()
{
    int i, j;
    HashTable h(11, 11);
    h.createHT();
    h.htOut();
    cout << "输入待查元素:" << '\n';
    cin >> i;
    j = h.searchHT(i);
    if (j >= 0)
        cout << "查找成功，下标值是:" << j;
    else
        cout << "查找失败";
    cout << '\n';
}